package dmsxl.tanxin;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Author: Zhang Dongwei
 * Date: 2023/8/1 13:53
 */
public class tx20_56 {

    public static void main(String[] args) {
//        LinkedList<String> list = new LinkedList<>();
//        list.add("Java");
//        list.add("C++");
//        list.add("Python");
//        String last = list.getLast();
//        System.out.println(last);  // Python
//        System.out.println(list.size());
//        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] intervals = {{2, 3}, {2, 2}, {3, 3}, {1, 3}, {5, 7}, {2, 2}, {4, 6}};
        int[][] res = merge(intervals);
        for (int i = 0; i < res.length; i++) {
            System.out.println(Arrays.toString(res[i]));
        }
    }

    public static int[][] merge1(int[][] intervals) {
        List<int[]> res = new LinkedList<>();
//        左边界排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
//        最小左边界
        int start = intervals[0][0];
        int rightmostRightBound = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
//            如果左边界大于最大右边界
            if (intervals[i][0] > rightmostRightBound) {
//                计入区间，更新start
                res.add(new int[]{start, rightmostRightBound});
                start = intervals[i][0];
                rightmostRightBound = intervals[i][1];
            } else {
//                更新最大右边界
                rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
            }
        }
        res.add(new int[]{start, rightmostRightBound});
        return res.toArray(new int[res.size()][]);
    }

    public static int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
//        左边界排序
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            else return a[0] - b[0];
        });
        res.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] temp = new int[2];
            if (intervals[i][0] <= res.getLast()[1]) {
                temp[0] = res.getLast()[0];
                temp[1] = Math.max(intervals[i][1], res.getLast()[1]);
                res.removeLast();
                res.add(temp);
            } else {
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
